package leetcode_400;


/**
 *@author 周杨
 *GuessNumberHigherOrLowerII_375_ 猜数字游戏 不管结果是什么  给出最小付出
 *describe:极大极小值方法 加上动态规划 AC 95% 好题目
 *see:https://www.cnblogs.com/grandyang/p/5677550.html
 *2018年7月10日 下午3:40:08
 */
public class GuessNumberHigherOrLowerII_375_ {
	int dp[][];
	
	public static void main(String[] args) {
		GuessNumberHigherOrLowerII_375_ test=new GuessNumberHigherOrLowerII_375_();
		System.out.println(test.guessNumber(10));
	}
	public int guessNumber(int n) {
		this.dp=new int[n+1][n+1];
		return help(1,n);
    }
	
	/**
	 * describe:极大极小值方法  每次划分两个区域 增加备忘录 AC 95%
	 * 2018年7月10日 下午3:24:53
	 */
	public int help(int l,int r) {
		if(l>r||l==r)
			return 0;
		if(r-l==1){
            dp[l][r]=l;
			return l;
        }
		if(r-l==2){
            dp[l][r]=l+1;
			return l+1;
        }
		int min=Integer.MAX_VALUE;
		for(int i=l;i<r;++i) {
			int left=i+(dp[l][i-1]!=0?dp[l][i-1]:help(l,i-1));
			int right=i+(dp[i+1][r]!=0?dp[i+1][r]:help(i+1,r));
			min=Math.min(Math.max(left, right), min);
		}
		this.dp[l][r]=min;
		return min;
	}
	
	
	 /**
	 * describe:没有备忘录 超时
	 * 2018年7月10日 下午3:36:09
	 */
	public int help1(int l,int r) {
			if(l>r||l==r)
				return 0;
			if(r-l==1)
				return l;
			if(r-l==2)
				return l+1;
			int min=Integer.MAX_VALUE;
			for(int i=l;i<=r;++i) {
				int left=i+help(l,i-1);
				int right=i+help(i+1,r);
				min=Math.min(Math.max(left, right), min);
			}
			return min;
		}
	
	
}
